<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>algorithm(前端常用算法)</title>
</head>
<body>
  <script>
    // 算法一： 打乱数组
    var arr = [1, 2, 3, 4, 5, 6, 7];
    arr.sort(function() {
        return (0.5 - Math.random());
    });
    console.log(arr);

    // 算法二：随机生成指定长度的字符串
    function randomString(n) {
      // 将随机范围设置成小写字母和数字
      let str = 'abcdefghijklmnopqrstuvwxyz0123456789';
      let [ret, i, len] = ["", 0, str.length];
      for (i = 0; i < n; i++) {
        ret += str.charAt(Math.floor(Math.random() * len));
      }
      return ret;
    }
    console.log(randomString(10)) // 随机生成8位字符串

    // 算法三： 数组间的交集、并集和差集
    var array1 = [1, 2, 3]
    var array2 = [2, 3, 4, 5]

    // 并集
    let union = new Set([...array1, ...array2]);
    console.log(...union) // 1,2,3,4,5

    // 交集
    let intersect = new Set([...array1].filter( x => new Set(array2).has(x)));
    console.log(...intersect) // 2,3

    // 差集
    let difference = new Set([...array1].filter(x => !new Set(array2).has(x)));
    console.log(...difference) // 1

    // 算法四： 求数组成员的最大值、最小值和平均值
    var arr = [1, 2, 3, 4, 5]
    Array.prototype.max = function(){
      var max = Math.max.apply(null,this)
      return max
    }

    console.log(arr.max()) // 最大值5

    Array.prototype.min = function(){
      var min = Math.min.apply(null,this)
      return min
    }

    console.log(arr.min()) // 最小值1

    Array.prototype.average = function () {
      let sum = this.reduce((sum, count) => {
        return sum + count
      }, 0)
      return sum / this.length
    }

    console.log(arr.average()) // 平均值3

    // 算法四：数组扁平化
    let arr4 = [1, [2, [3, 4]]];
 
    function flattern(arr) {  // 方法1、递归
      let result = [];
      arr.forEach((item) => {
        if(Array.isArray(item)){   // 需要注意Array.isArray()方法不兼容IE6-IE8
          result = result.concat(flattern(item));
        }else{
          result.push(item);
        }
      })
      return result;
    }
    console.log(flattern(arr4));

    function flatten2(arr) { // 方法2、toString()
      return arr.toString().split(',').map(function(item){
          return +item // +可以快速获得Number类型
      })
    }

    console.log(flatten2(arr4))

    function flatten3(arr) { // 方法3、reduce()
      return arr.reduce(function(prev, next){
          return prev.concat(Array.isArray(next) ? flatten3(next) : next)
      }, [])
    }
 
    console.log(flatten3(arr4))

    // 算法五、深度优先和广度优先搜索
    const root = [
    {
      "id":1,
      "pid":null,
      "key":1,
      "title":"1-1111",
      "children":[
        {
          "id":2,
          "pid":1,
          "key":2,
          "title":"2-1111",
          "children":[
            {
              "id":4,
              "pid":2,
              "key":4,
              "title":"8-1111",
              "children":[]
            },
            {
              "id":5,
              "pid":2,
              "key":5,
              "title":"9-1111",
              "children":[
                {
                  "id":7,
                  "pid":5,
                  "key":7,
                  "title":"5-1111",
                  "children":[]
                },
                {
                  "id":8,
                  "pid":5,
                  "key":8,
                  "title":"8-1111",
                  "children":[]
                },
              ]
            },
            {
              "id":6,
              "pid":2,
              "key":6,
              "title":"10-1111",
              "children":[]
            },
          ]
        },
        {
          "id":3,
          "pid":1,
          "key":3,
          "title":"9-1111",
          "children":[]
        }
      ]
    }
  ]

  // 深度优先遍历-递归
  const depthFirstSearch = source => {
    const result = []; // 存放结果的数组
    // 递归方法
    const dfs = data => {
      // 遍历数组
      data.forEach(element => {
        // 将当前节点 id 存放进结果
        result.push(element.id);
        // 如果当前节点有子节点，则递归调用
        if (element.children && element.children.length > 0) {
          dfs(element.children);
        }
      });
    };
    dfs(source);
    return result;
  };
 
  const s = depthFirstSearch(root)
  console.log(s);// 结果为 [1, 2, 4, 5, 7, 8, 6, 3]

  // 深度优先遍历-栈实现  
  const depthFirstSearch2 = source => {
    const result = []; // 存放结果的数组
    // 当前栈内为全部数组
    const stack = JSON.parse(JSON.stringify(source));
    // 循环条件，栈不为空
    while (stack.length !== 0) {
      // 最上层节点出栈
      const node = stack.shift();
      // 存放节点
      result.push(node.id);
      node.children.slice().reverse().forEach(
        child => stack.unshift(child) // 从头部插入进栈元素
      )
      
    }
    return result;
  };
 
  const s1 = depthFirstSearch2(root)
  console.log(s1); // 结果为 [1, 2, 4, 5, 7, 8, 6, 3]

  // 广度优先遍历
  const breadthFirstSearch = source => {
    const result = []; // 存放结果的数组
    // 当前队列为全部数据
    const queue = JSON.parse(JSON.stringify(source));
    // 循环条件，队列不为空
    while (queue.length > 0) {
      // 第一个节点出队列
      const node = queue.shift();
      result.push(node.id); // 存放结果数组
      node.children.forEach(
        child => queue.push(child)
      )
    }
    return result;
  };
 
  const s2 = breadthFirstSearch(root)
  console.log(s2);// 结果为 [1, 2, 3, 4, 5, 6, 7, 8]
  </script>
</body>
</html>